package org.nowcoder.leetcode.bit;

/**
 * Title  : 69. Sqrt(x)
 * Source : https://leetcode.cn/problems/sqrtx/?envType=study-plan-v2&envId=top-interview-150
 * Author : XrazYang
 * Date   : 2023-08-24
 */
public class LeetCode_69 {
    public int mySqrt(int x) {
        if (x == 0) return 0;
        if (x == 1) return 1;
        int l = 0, r = x / 2;
        int result = -1;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (((long) mid * mid) <= x) {
                result = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return result;
    }
}
